import java.util.Objects;

public class Solution {

    /**
     * 给你一个链表数组，每个链表都已经按升序排列。
     * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        } else if (lists.length == 1) {
            return lists[0];
        }

        ListNode left = lists[0];
        for (int i = 1; i < lists.length; i++) {
            ListNode right = lists[i];
            left = merge(left,right);
        }

        return left;
    }

    public ListNode merge(ListNode left, ListNode right) {
        ListNode result;
        ListNode temp = null;
        if (Objects.isNull(left)) {
            return right;
        }
        if (Objects.isNull(right)) {
            return left;
        }
        if (left.val > right.val) {
            temp = left;
            left = right;
            right = temp;
        }
        result = left;

        while (Objects.nonNull(left) && Objects.nonNull(right)) {
            if (left.val <= right.val) {
                temp = left;
                left = left.next;
            } else {
                temp.next = right;
                right = right.next;
                temp = temp.next;
                temp.next = left;
            }
        }

        if (Objects.isNull(left)){
            temp.next = right;
        }

        return result;
    }

}
